# @Time    : 2020/11/17 2:26 下午
# @Author  : baii
# @File    : array_list
# @Use     : python 模拟实现动态数组
class ArrayList(object):

    def __init__(self, capacity: int =10):
        # 这里使用list 效果就假装等价于java 的泛型了
        self.__data = list()
        self.__capacity = capacity
        self.__size = 0

    # 获取当前最大容量
    def get_capacity(self) -> int:
        return self.__capacity

    # 获取数组元素个数
    def __len__(self) -> int:
        return self.__size

    # 是否为空
    def is_empty(self) -> bool:
        return len(self.__data) == 0

    # 在指定索引处插入数据
    def insert(self, index: int, data):
        if index < 0 or index > self.__size:
            raise Exception("Add failed. Require index >= 0 and index <= size.")

        # 判断是否需要触发扩容
        if self.__size == self.__capacity:
            self.__resize(self.__capacity * 2)

        # 移动原有元素
        for idx in range(self.__size, index, -1):
            self.__data[idx + 1] = self.__data[idx]

        self.__data[index] = data
        self.__size += 1

    def add_last(self, data):
        self.insert(self.__size, data)

    def add_first(self, data):
        self.insert(0, data)

    def get(self, index: int):
        if index < 0 or index > self.__size:
            raise Exception("Get failed. Index is illegal.")
        return self.__data[index]

    # 修改index索引位置的元素为data
    def set(self, index: int, data):
        if index < 0 or index > self.__size:
            raise Exception("Set failed. Index is illegal.")
        self.__data[index] = data

    # 相当于java 的 contains
    def __eq__(self, other) -> bool:
        for data in self.__data:
            if data == other:
                return True
        return False

    # 查找数组中元素 other 所在的索引，如果不存在元素 other，则返回-1
    def find(self, other) -> int:
        for idx, data in enumerate(self.__data):
            if data == other:
                return idx
        return -1

    # 从数组中删除index位置的元素, 返回删除的元素
    def remove(self, index: int):
        if index < 0 or index > self.__size:
            raise Exception("remove failed. Require index >= 0 and index <= size.")

        # 移动原有元素
        for idx in range(index, self.__size):
            self.__data[idx - 1] = self.__data[idx]

        ret = self.__data.pop()
        self.__size -= 1
        # 判断是否需要缩容，这里注意复杂度震荡问题
        if (self.__size == self.__capacity // 4):
            self.__resize(self.__capacity // 2)
        return ret

    def remove_first(self):
        return self.remove(0)

    def remove_last(self):
        return self.remove(self.__size - 1)

    def remove_element(self, e):
        index = self.find(e)
        if index != -1:
            self.remove(index)

    def __resize(self, new_capacity: int):
        new_datas = list()
        for data in self.__data:
            new_datas.append(data)

        self.__data = new_datas
        self.__capacity = new_capacity

    def __str__(self) -> str:
        return f"Array: size = {self.__size} , capacity = {self.__capacity}\n"

